﻿using System;
using System.Collections;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;

namespace GraphWork
{
    [Serializable]
    internal class Graph
    {
        public Graph()
        {
            _matrixGraph = new int[0, 0];
            used = new int[0];
        }

        public int[,] _matrixGraph { get; set; }
        public int[] used;
        public int[] dist { get; set; }
        public int[] path { get; set; }
        public int[] dfs_result { get; set; }

        /// <summary>
        /// Печатает матрицу смежности
        /// </summary>
        public void PrintMatrix()
        {
            if (_matrixGraph.GetLength(0) == 0)
            {
                Console.WriteLine("Матрица не заполнена!");
                return;
            }

            Console.WriteLine("\n Матрица смежности: ");
            Console.Write("\n\t");
            for (int i = 0; i < _matrixGraph.GetLength(0); i++)
            {
                Console.Write("{0}\t", i);
            }
            Console.WriteLine();
            for (int i = 0; i < _matrixGraph.GetLength(0); i++)
            {
                Console.Write("{0}\t", i);
                for (int j = 0; j < _matrixGraph.GetLength(0); j++)
                {
                    Console.Write("{0}\t", _matrixGraph[i, j]);
                }
                Console.WriteLine();
            }
        }

        /// <summary>
        /// изменение размеров матрицы
        /// </summary>
        private static void MatrixResize(ref Graph item, int mode)
        {
            switch (mode)
            {
                case 1:
                    var tmp = new int[item._matrixGraph.GetLength(0)+1,item._matrixGraph.GetLength(1) + 1];
                    for (int i = 0; i < tmp.GetLength(0); i++)
                    {
                        for (int j = 0; j < tmp.GetLength(1); j++)
                        {
                            tmp[i, j] = -1;
                        }
                    }
                    Array.Copy(item._matrixGraph, tmp, item._matrixGraph.Length);
                    item._matrixGraph = tmp;
                    break;
                case -1:
                    int[,] tmp1 = new int[item._matrixGraph.GetLength(0) - 1,item._matrixGraph.GetLength(1) - 1];
                    for (int i = 0; i < tmp1.GetLength(0); i++)
                    {
                        for (int j = 0; j < tmp1.GetLength(1); j++)
                        {
                            tmp1[i, j] = -1;
                        }
                    }
                    Array.Copy(item._matrixGraph, tmp1, item._matrixGraph.Length);
                    item._matrixGraph = tmp1;
                    break;
            }
        }

        /// <summary>
        /// добавить вершину
        /// </summary>
        public void AddTop(ref Graph item, int[] edge, int[] weight)
        {
              MatrixResize(ref item, 1);
        }

        /// <summary>
        /// удалить вершину
        /// </summary>
        public void RemoveTop(ref Graph item, int rmTop)
        {
            var tmp = new int[item._matrixGraph.GetLength(0), item._matrixGraph.GetLength(0)];
            Array.Copy(item._matrixGraph, tmp, item._matrixGraph.Length);
            MatrixResize(ref item, -1);

            for (int i = 0, n = 0; i < item._matrixGraph.GetLength(0); i++, n = 0)
            {
                for (int j = 0, m = 0; j < item._matrixGraph.GetLength(0); j++, m++)
                {
                    if (i != rmTop || j != rmTop)
                    {
                        item._matrixGraph[n, m] = tmp[i, j];
                        n++;
                    }
                }
            }
        }

        /// <summary>
        /// добавить ребро
        /// </summary>
        public void AddEdge(ref Graph item, int start, int finish, int weigth)
        {
            item._matrixGraph[start, finish] = weigth;
        }


        /// <summary>
        /// удалить ребро
        /// </summary>
        public void RemoveEdge(int s, int f)
        {
            try
            {
                if (_matrixGraph != null) _matrixGraph[s, f] = 0;
            }
            catch
            {
                Console.WriteLine("Ошибка записи! Проверьте корректность данных!");
            }

        }

        /// <summary>
        /// изменить вес ребра
        /// </summary>
        public void ChangeWeigth(int s, int f, int w)
        {
            try
            {
                if (_matrixGraph != null) _matrixGraph[s, f] = w;
            }
            catch
            {
                Console.WriteLine("Ошибка записи веса! Проверьте корректность данных!");
            }
        }

        /// <summary>
        /// Сохранить граф в файл
        /// </summary>
        public void SaveGraph()
        {
            var bf = new BinaryFormatter();
            FileStream fs = null;
            try
            {
                fs = new FileStream("data.bin", FileMode.Create, FileAccess.Write);
                bf.Serialize(fs, this);
            }
            catch
            {
                Console.WriteLine("Ошибка доступа к файлу!");
                return;
            }
            finally
            {
                if (fs != null) fs.Close();
            }
        }

        /// <summary>
        /// Загрузить граф из файла
        /// </summary>
        public Graph LoadGraph(ref Graph item)
        {
            var bf = new BinaryFormatter();
            FileStream fs = null;
            try
            {
                fs = new FileStream("data.bin", FileMode.Open, FileAccess.Read);
                item = (Graph)bf.Deserialize(fs);
            }
            catch
            {
                Console.WriteLine("Ошибка доступа к файлу!");
            }
            finally
            {
                if (fs != null) fs.Close();
            }
            return item;
        }

        public void Dfs(int source)
        {
            try
            {
                used[source] = 1;
                Console.WriteLine(source + " ");

                for (int i = 1; i < _matrixGraph.GetLength(0); i++)
                {
                    if (_matrixGraph[source, i] != 0 && used[i] != 0)
                        Dfs(i);
                }
            }
            catch
            {
                Console.WriteLine("Неверно задано значение(вершины или графа)!");
            }
        }

         public ArrayList SearchOstov()
        {
            var list = new ArrayList {1};
             for (int i = 0; i < _matrixGraph.GetLength(0) - 1; i++)
            {
                double Min = 10000;
                int k=0;
                for (int j = 0; j < _matrixGraph.GetLength(1); j++)
                {
                    if (_matrixGraph[0, j] != -1)
                    {
                        if (_matrixGraph[0, j] < Min)
                        {
                            Min = _matrixGraph[0, j];
                            k = j;
                        }
                    }
                }
                list.Add(_matrixGraph[0, k]);
                for (int j = 0; j < _matrixGraph.GetLength(1); j++)
                {
                    if ((_matrixGraph[k, j] != -1) && (_matrixGraph[0, j] != -1))
                    {
                        _matrixGraph[0, j] = Convert.ToInt32(Math.Min(_matrixGraph[0, j], _matrixGraph[k, j]));
                    }
                }
                _matrixGraph[0, k] = -1;
                list.Add(k + 1);
            }
            return list;
        }

        public void SearchNearPath()
        {
        }
    }

    internal class Program
    {
        private static int MenuSelect()
        {
            int ch = -1;
            Console.WriteLine("\n1. Добавить вершину");
            Console.WriteLine("2. Удалить вершину");
            Console.WriteLine("3. Добавить ребро");
            Console.WriteLine("4. Удалить ребро");
            Console.WriteLine("5. Изменить вес ребра");
            Console.WriteLine("6. Сохранить граф и результаты в файл");
            Console.WriteLine("7. Загрузить граф и результаты из файла");
            Console.WriteLine("8. Поиск в глубину");
            Console.WriteLine("9. Поиск минимального оставного дерева");
            Console.WriteLine("10. Поиск кратчайшего пути");
            Console.WriteLine("11. Сохранить результаты расчетов в файл");
            Console.WriteLine("12. Загрузить результаты расчета из файла");
            Console.WriteLine("13. Печать матрицы смежности");
            Console.WriteLine("0. Выход");
            do
            {
                Console.Write("\nВаш выбор -> ");
                string tmp = Console.ReadLine();
                if (!String.IsNullOrEmpty(tmp))
                   ch = Convert.ToInt32(tmp);
            } while (ch < 0 || ch > 13);
            Console.WriteLine("");
            return ch;
        }

        private static void Main()
        {
            var gr = new Graph();
            //gr.LoadGraph(ref gr);
            for (; ; )
            {
                switch (MenuSelect())
                {
                    case 1:
                        var weigth = new int[0];
                        var edge = new int[0];
                        gr.AddTop(ref gr, edge, weigth);
                        Console.WriteLine("Веришина добавлена!\n");
                        gr.PrintMatrix();
                        break;
                    case 2:
                        Console.WriteLine("Введите номер удаляемой вершины (от 0 до {0})", gr._matrixGraph.GetLength(0) - 1);
                        int rmTop = Convert.ToInt32(Console.ReadLine());
                        gr.RemoveTop(ref gr, rmTop);
                        break;
                    case 3:
                        int topstart, topfinish, wth;
                        do
                        {
                            Console.Write("Введите вершину (от 0 до {0}) ИЗ которой выходит ребро -> ",
                                          gr._matrixGraph.GetLength(0) - 1);
                            topstart = Convert.ToInt32(Console.ReadLine());
                        } while (topstart < 0 || topstart > gr._matrixGraph.GetLength(0) - 1);
                        do
                        {
                            Console.Write("Введите вершину (от 0 до {0}) в которую ВХОДИТ ребро -> ", gr._matrixGraph.GetLength(0) - 1);
                            topfinish = Convert.ToInt32(Console.ReadLine());
                        } while (topfinish < 0 || topfinish > gr._matrixGraph.GetLength(0) - 1);

                        do
                        {
                            Console.Write("Введите вес нового ребра-> ");
                            wth = Convert.ToInt32(Console.ReadLine());
                        } while (wth < 0);

                        gr.AddEdge(ref gr, topstart, topfinish, wth);
                        Console.WriteLine("Ребро добавлено!");
                        break;
                    case 4:
                        Console.Write("Для удаления ребра, введите номер стартовой вершины -> ");
                        int s = Convert.ToInt32(Console.ReadLine());
                        Console.Write("\nВведите номер конечной вершины -> ");
                        int f = Convert.ToInt32(Console.ReadLine());
                        gr.RemoveEdge(s, f);
                        Console.WriteLine("Ребро удалено!");
                        break;
                    case 5:
                        Console.Write("Для изменения веса ребра, введите номер стартовой вершины -> ");
                        int sw = Convert.ToInt32(Console.ReadLine());
                        Console.Write("\nВведите номер конечной вершины -> ");
                        int fw = Convert.ToInt32(Console.ReadLine());
                        Console.Write("Введите новые вес -> ");
                        int ww = Convert.ToInt32(Console.ReadLine());
                        gr.ChangeWeigth(sw, fw, ww);
                        Console.WriteLine("Вес изменен!");
                        break;

                    case 6:
                        gr.SaveGraph();
                        Console.WriteLine("Граф сохранен!\n");
                        break;
                    case 7:
                        gr.LoadGraph(ref gr);
                        Console.WriteLine("Граф загружен!\n");
                        break;
                    case 8:
                        Console.Write("Введите стартовую вершину (от 0 до {0})-> ", gr._matrixGraph.GetLength(0));
                        int ch = Convert.ToInt32(Console.ReadLine());
                        Console.WriteLine("Вершины посещенные при обходе в глубину: ");
                        gr.Dfs(ch);
                        break;
                    case 9:
                        ArrayList ar = gr.SearchOstov();
                        Console.WriteLine("Минимальное оставное дерево: ");
                        for (int i = 0; i < ar.ToArray().Length; i++)
                        {
                            Console.Write(ar[i] + " ");
                        }
                        Console.WriteLine("\n");
                        break;
                    case 10:
                        Console.Write("Введите стартовую вершину: ");
                        int start = Convert.ToInt32(Console.ReadLine());
                        var tmp = new Dijkstra(gr._matrixGraph, start-1);
                        Console.Write("\n Введите конечную вершину: ");
                        
                        int[] d = tmp.dist;
                        int[] p = tmp.path;
                        foreach (int t in d)
                        {
                            Console.WriteLine(t);
                        }
                        foreach (int t in p)
                        {
                            Console.WriteLine(t);
                        }
                        break;
                    case 11:
                        gr.SaveGraph();
                        Console.WriteLine("Граф и результаты работы алгоритмов (если они есть) - сохранены в файл Data.bin");
                        break;
                    case 12:
                        gr.LoadGraph(ref gr);
                        Console.WriteLine("Результаты расчетов и граф загружены из файла!");
                        break;
                    case 13:
                        gr.PrintMatrix();
                        break;
                    case 0:
                        return;
                }
            }
        }
    }
}

 